import java.util.ArrayList;
import java.util.List;

public class ReorderList {

    public void reorderList1(ListNode head) {
        ListNode temp = head;
        List<ListNode> list = new ArrayList<>();
        int len = 0;
        while (temp != null) {
            ++len;
            list.add(temp);
            temp = temp.next;
        }
        int l = 0;
        int r = len - 1;
        temp = new ListNode();
        while (l < r) {
            temp.next = list.get(l++);
            temp.next.next = list.get(r--);
            temp = temp.next.next;
        }
        if (r == l) {
            temp.next = list.get(l);
        }
        list.get(l).next = null;
    }

    public void reorderList(ListNode head) {
        ListNode mid = findMid(head);
        ListNode temp = mid.next;
        mid.next = null;
        ListNode reverse = reverse(temp);
        mergeList(head, reverse);
    }

    public ListNode reverse(ListNode head) {
        if (head == null) return null;
        ListNode dummyHead = new ListNode();
        ListNode temp = head;
        while (temp != null) {
            ListNode next = temp.next;
            temp.next = dummyHead.next;
            dummyHead.next = temp;
            temp = next;
        }
        return dummyHead.next;
    }

    public ListNode mergeList(ListNode node1, ListNode node2) {
        ListNode dummyHead = new ListNode();
        ListNode temp = dummyHead;
        ListNode l = node1;
        ListNode r = node2;
        while (l != null && r != null) {
            temp.next = l;
            l = l.next;
            temp.next.next = r;
            r = r.next;
            temp = temp.next.next;
        }
        temp.next = l == null ? r : l;
        return dummyHead.next;
    }

    public ListNode findMid(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}
